package com.example.leetcode.prcatice;

import java.util.Arrays;

/**
 * 给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
 *
 * <p>数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。
 *
 * <p>你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
 *
 * <p>在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-absolute-sum-difference
 */
public class Test1818 {
    /**
     * 思路，复制一个nums1的数组，并对其进行排序
     * 将nums1[i] - nums2[i] 的绝对差值加起来sum
     * 对每个nums1[i]的值去复制的数组利用二分查找去和nums[2]最近的值，并记录下来他们的差值
     * 对每个记录下来的差值取出最大的一个，利用sum-减去它即可
     * @param nums1
     * @param nums2
     * @return
     */
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] st = nums1.clone();
        Arrays.sort(st);
        long s = 0, mx = 0;
        for (int i = 0; i < n; ++i) {
            int x = nums1[i], y = nums2[i];
            int z = Math.abs(x - y);
            s += z;
            int left = 0, right = n - 1;
            while (left < right) {
                int mid = left + right >> 1;
                if (st[mid] < y)
                    left = mid + 1;
                else
                    right = mid;
            }
            mx = Math.max(mx, z - Math.min(Math.abs(st[left] - y), (left - 1 > 0 ? Math.abs(st[left - 1] - y) : z)));
        }
        return (int) ((s - mx) % 1000000007);


    }


}

class Demo1818{
  public static void main(String[] args) {
    int[] nums1 = {1,10,4,4,2,7};
    int[] nums2 = {9,3,5,1,7,4};
    Test1818 t = new Test1818();
    t.minAbsoluteSumDiff(nums1,nums2);
  }
}